Digital technology is used to transmit, store, display, and print continuous tone ("grey-scale") images. To that end, the image to be printed is typically represented as a sequence of digits, each representing the density of a corresponding elemental portion of the image (a "picture element" or "pixel").
Considerable economies in the resources used to store and transmit image data can be achieved by "compressing" the image data. Known prior art image compression schemes include "JBIG" for bilevel images (eg, line drawings), and "JPEG" for continuous tone images (eg, photographs). Normally, image compression is "lossy" and will result in some degradation of image quality; however, even a lossy compression algorithm can be made "lossless" by comparing the degraded image after compression with the original image prior to compression to generate error data representing some or all of the data lost during compression. The error data can be compressed using a conventional lossless data-oriented compression scheme such as run-length encoding and appended to the compressed data representing the degraded image. For ephemeral display applications, it is usually sufficient to use a lossy compression scheme to transmit the image during a "browse" mode, and to use error data to reconstruct a more accurate version of the original image only when it is to be printed or otherwise archived.
JBIG, JPEG, and other prior art compression schemes for digital images are described in detail in Chapter 6 of "Managing Gigabytes" by Ian H. Witten et al (Van Nostrand Reinhold, N.Y., 1994), as well as in commonly assigned U.S. Pat. No. 5,245,679 and the various references discussed therein, which are hereby incorporated in their entirety by reference.
Since most conventional digital printing technologies (such as thermal ink-jet) and many digital display technologies (such as plasma) are restricted to rendering a given portion of the printed image as bilevel images in which any given area is either black (eg, covered with ink) or white (eg, free of ink), it is conventional to render intermediate grey-scale levels as "half-tone screens" having varying proportions of black and white areas. In order to avoid visible artifacts resulting from regular geometric relationships of the black and white areas with regular geometric elements in the original image, it is also conventional to randomize the size, shape and/or location of the individual areas.
Particularly when the resolution of the image forming process (eg, the size of the smallest solid area that can be covered with ink) is of the same order of magnitude as the resolution of the digitization of the image (size of an individual pixel), a dither matrix having different predetermined thresholds in each of its cells may be used to replace each input pixel in the original grey-scale image with a corresponding black or white output pixel, such that if the grey level of an input pixel is less or more than the threshold in the corresponding cell of the dither matrix, it is replaced in the printed image by a white or black pixel, respectively. Thus, different distributions of pixels will be generated for portions of the image having different levels of intensity.
However, because best results are obtained when the dithering process introduces "blue noise" into the image, for example by using a large dither matrix having a somewhat randomized distribution of thresholds, and because "pure" noise is inherently incompressible, the known bilevel image compression algorithms such as JBIG and conventional data compression algorithms such as LZW and Arithmetic Encoding will provide at best only a slight additional compression of continuous tone image data that has previously been processed into a bilevel image by an optimally randomized dither matrix. Conversely, use of the known continuous tone image data compression algorithms such as JPEG to compress the image data before it is dithered is believed to be inherently inefficient, because in most cases the undithered image will contain more information that the dithered image.
"Dithering with Blue Noise" and other halftone representations of a grey-scale image are described in detail in Chapter 8 of "Digital Halftoning" by Robert Ulichney (The MIT Press, Cambridge Mass., 1987) and the various references discussed therein, which are hereby incorporated in their entirety by reference.